package com.sfx.算法专题.二分查找.A总结题型;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: sfx
 * Date: 2023-08-03
 * Time: 21:28
 */
public class A总结题型 {
/**
 *  1. 朴素二分模板
 *       1): 基本思想
 *           如果满足 二段性 我们就可以使用二分查找的算法来解决
 *           二段性 : 当我们找到一定规律,选取某一个点之后,我们能把数组划分为两个部分,这就是二段性
 *           二分查找 的本质是 "就二段性"
 *           只要数组有二段性的时候 or 数组无序,但有二段性,就可以使用二分查找
 *       2): 伪代码-->算法模板
 *           while(left <= right)
 *               int mid = (right - left) / 2 + left; //防止溢出方式
 *               if(.....)  right = mid -1;
 *               else if(.....) left = mid + 1;
 *               else return  .....
 *           return -1;
 *       3): 注意事项 :
 *            1. 循环的结束条件
 *                  left>right结束, 因为我们寻找的left...right区间的数字是未知的所以,我们最后一个left=right
 *                  的时候,我们并不能判断这个数字是否合法
 *            2. 二分查找为什么是正确的?
 *                  二分查找本就是暴力解法的优化,只不过是暴力解法每次干掉一个数字,而二分查找是根据
 *                  二段性一次 "干掉 "一批数字
 *            3. 时间复杂度?
 *                  时间复杂度主要取决于循环次数
 *                  第1次循环 : 区间划分为 n / 2   n / 2^1
 *                  第2次循环 : 区间划分为 n / 4   n / 2^2
 *                  第3次循环 : 区间划分为 n / 8   n / 2^3
 *                  第4次循环 : 区间划分为 n / 16  n / 2^4
 *                  ...
 *                  第x次循环 : 区间为 1   --> left==right的情况  n / 2^x
 *                  所以时间复杂度为  n/2 ^x = 1   x =log N
 *            logN 为什么快 ? 2^32 = 42亿  如果使用二分查找是 32次
 *            4. 计算中间点如何计算 ?
 *                mid = (left + right) / 2 有溢出风险
 *                mid = (right - left) / 2 + left  避免溢出
 *                right - left 计算出区间长度  除以2就是中间点 ,left在向右移动就是中间点就是中间位置了
 *    2. 查找区间的左端点 t=3
 *       1  2  3  3  3  4  5
 *       [  ]  [           ]
 *       < 3     >=3
 *       2.1 我们把区间分为两个部分 < target 和 >= target
 *       2.2 为什么合二为一了呢 ? 因为 我们要查找区间左端点,
 *           可能第一次我们就找到与target相同的值了,但是他并不是左端点
 *           所以,我们相等的时候,我们不能直接返回
 *           x < target  left = mid + 1   [left,mid + 1]
 *           x >= target right = mid      [mid,right]
 *       2.3 细节处理
 *           2.3.1  循环条件处理
 *                left <= right   ×
 *                left < right    √
 *                原因是 :
 *                   1): left == right 的时候已经能够确定答案了,不需要在判断了
 *                   2): 如果在left==right的时候 进入 x>=target的条件下就会进入死循环
 *           2.3.2 计算中点操作.
 *                left + (right - left) / 2      √  ->左端点
 *                left + (right - left + 1) / 2  ×  ->右端点
 *                原因是 :
 *                   1): 比如只剩下两个数的时候,如果使用求右端点的那个就会陷入死循环
 *    3. 查找区间的右端点 t=3
 *       1  2  3  3  3  4  5
 *       [           ]  [  ]
 *            <=3        >3
 *       3.1 我们把区间分为两个部分 <= target 和 > target
 *       3.2 为什么合二为一了呢 ? 因为 我们要查找区间右端点,
 *           可能第一次我们就找到与target相同的值了,但是他并不是右端点
 *           所以,我们相等的时候,我们不能直接返回
 *           x <= target  left = mid            [mid,right]
 *           x > target   right = mid - 1       [left, mid - 1]
 *       3.3 细节处理
 *           3.3.1  循环条件处理
 *                left <= right   ×
 *                left < right    √
 *                原因是 :
 *                   1): left == right 的时候已经能够确定答案了,不需要在判断了
 *                   2): 如果在left==right的时候 进入 x<=target的条件下就会进入死循环
 *           3.3.2 计算中点操作.
 *                left + (right - left) / 2      ×  ->左端点
 *                left + (right - left + 1) / 2  √  ->右端点
 *                原因是 :
 *                   1): 比如只剩下两个数的时候,如果使用求左端点的那个就会陷入死循环
 *
 *
 *       技巧 : 就是找二段性,满足某种性质 --> 二段性,能够把数组分成两个部分
 *             比如 : >x  <=x
 *                   >=x  <x
 *             数组有序,看呢过不能找出二段性,找到一个点进行分析,分为两段区间
 */
}